import javafx.scene.shape.HLineTo;
import sun.net.www.protocol.http.HttpURLConnection;
import sun.plugin.cache.CacheUpdateHelper;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author kaho
 * @since 2021/5/10
 */
public class LCP_12_小张刷题计划 {

    public static void main(String[] args) {
        LCP_12_小张刷题计划 test = new LCP_12_小张刷题计划();
//        int i = test.minTime(new int[]{1, 2, 3, 3}, 2);
        int i = test.minTime(new int[]{1, 2, 3}, 3);
//        boolean check = test.check4(new int[]{1, 2, 3, 3}, 2, 2);
//        boolean check = test.check4(new int[]{1, 2, 3}, 3, 0);
    }
    /**
     * 为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。
     * <p>
     * 在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。
     * <p>
     * 我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param time
     * @param m
     * @return
     */
    public int minTime(int[] time, int m) {
        int l = 0, r = Integer.MAX_VALUE;
        while (l<r){
            int mid = l + (r - l) / 2;
            if(check4(time, m, mid)){
                r = mid;
            }else {
                l = mid-1;
            }
        }
        return l;
    }

    private boolean check4(int[] time, int m, int mid) {
        int curTime = mid;
        int flag = 1;
        int max = time[0];
        int curM = 0;
        for (int i = 0; i < time.length;) {
            max = Math.max(max, time[i]);
            if (time[i]<=curTime){
                curTime-=time[i];
                i++;
            }else {
                if (flag==1){
                    curTime+=max;
                    flag=0;
                    if (curTime>=time[i]){
                        curTime-=time[i];
                        i++;
                    }else {
                        curM++;
                        if (curM>=m){
                            return false;
                        }
                        curTime = mid;
                        flag = 1;
                        max= time[i];
                    }
                }else {
                    curM++;
                    if (curM>=m){
                        return false;
                    }
                    curTime = mid;
                    flag = 1;
                    max= time[i];
                }
            }
        }
        return true;
    }


    public int minTime3(int[] time, int m) {
        int l = 0, r = Integer.MAX_VALUE;

        while (l<r){
            int mid = l + (r - l) / 2;
            if(check3(time, m ,mid)){
                r = mid;
            }else {
                l = mid+1;
            }
        }
        return l;
    }

    private boolean check3(int[] time, int m, int mid) {
        int curT  = mid;
        int help = 0;
        int curMax = time[0];
        int day = 0;
        for (int i = 0; i < time.length;) {
            curMax = Math.max(curMax, time[i]);
            if(curT<time[i]){
                if (help==0){
                    curT += curMax;
                    help++;
                    if (curT<time[i]){
                        curT = mid;
                        help = 0;
                        curMax = time[i];
                        day++;
                        if (day>=m) {
                            return false;
                        }
                    }else {
                        curT -=time[i];
                        i++;
                    }
                }else {
                    curT = mid;
                    help = 0;
                    curMax = time[i];
                    day++;
                    if (day>=m) {
                        return false;
                    }
                }
            }else {
                curT-=time[i];
                i++;
            }
        }
        return true;
    }




    public int minTime2(int[] time, int m) {
        int l = 0, r = Integer.MAX_VALUE;

        while (l<r){
            int mid = l + (r - l) / 2;
            if(check2(time,m,mid)){
                r = mid;
            }else {
                l = mid+1;
            }
        }
        return l;
    }

    private boolean check2(int[] time, int m, int mid) {
        int curT = mid;
        int day = 0;
        int help = 0;
        int curMax = 0;
        for (int i = 0; i < time.length;) {
            curMax = Math.max(curMax, time[i]);
            if (curT<time[i]){
                if (help == 0) {
                    curT+=curMax;
                    help++;
                    if (curT<time[i]){
                        curT = mid;
                        day++;
                        curMax = time[i];
                        help = 0;
                        if (day>=m){
                            return false;
                        }
                    }else {
                        curT-=time[i];
                        i++;
                    }
                }else {
                    curT = mid;
                    day++;
                    curMax = time[i];
                    help = 0;
                    if (day>=m){
                        return false;
                    }
                }
            }else {
                curT-=time[i];
                i++;
            }
        }
        return true;
    }


    public int minTime1(int[] time, int m) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        while (l<r){
            int mid = l+((r-l)>>2);
            if(check(time,m,mid)){
                r = mid;
            }else {
                l = mid+1;
            }
        }
        return l;
    }

    public boolean check(int[] time, int m, int t) {
        int curMax = time[0];
        int curT = t;
        int help = 0;
        int day = 0;
        for (int i = 0; i < time.length;) {
            curMax = Math.max(curMax, time[i]);
            if(curT<time[i]){
                if (help==0){
                    curT+=curMax;
                    help++;
                    if (curT<time[i]){
                       day++;
                       curMax=time[i];
                        curT = t;
                        help = 0;
                        if (day>=m) {
                            return false;
                        }
                    }else {
                        curT-=time[i];
                        i++;
                    }
                }else {
                    day++;
                    curMax = time[i];
                    curT = t;
                    help = 0;
                    if (day>=m) {
                        return false;
                    }
                }
            }else {
                curT -= time[i];
                i++;
            }
        }
        return true;
    }


    public boolean check1(int[] time, int m, int t) {
        int curT = t;
        int help = 0;
        int day = 0;
        int curMax = time[0];
        for (int i = 0; i < time.length;) {
            curMax = Math.max(curMax, time[i]);
            if(curT<time[i]){
                if (help==0) {
                    curT+=curMax;
                    help++;

                    if(curT >= time[i]){
                        curT -= time[i];
                        i++;
                    }else {
                        day++;
                        help = 0;
                        curT = t;
                        curMax = time[i];
                        if(day>m){
                            return false;
                        }
                    }
                }else {
                    day++;
                    help = 0;
                    curT = t;
                    curMax = time[i];
                    if(day>m){
                        return false;
                    }
                }
            }else {
                curT -= time[i];
                i++;
            }
        }

        return true;
    }
}
